package algo.A04_快速排序和归并排序;
import util.ArrayUtil;

/**
 * 双向扫描法
 * 双向扫描的思路是,头尾指针往中间扫3描,从左找到大于主元的元素,从右找到小于等于主元的元素二者交换,继续扫描,直到左侧无大元素,右侧无小元素
 */
public class M04_快速排序优化_绝对中值法 {
    public static void main(String[] args) {
        int[] arr = ArrayUtil.getRandomArr(10, 1, 50);
        ArrayUtil.print(arr);
        quickSort(arr, 0, arr.length - 1);
        ArrayUtil.print(arr);
    }

    /**
     * 快速排序
     * @param A 原数组
     * @param p 数组左侧下标
     * @param r 数组右侧下标
     */
    private static void quickSort(int[] A, int p, int r) {
        if (p < r) {
            int q = partition(A, p, r);//执行分区方法，获取中点下标，中点左侧的元素都比中点小，右边都比中点大
            quickSort(A, p, q - 1);//对中点左侧的元素再次调用快速排序
            quickSort(A, q + 1, r);//对中点右侧的元素再次调用快速排序
        }
    }

    /**
     * 分区方法-绝对中值优化
     * @param A 原数组
     * @param p 左侧数组下标
     * @param r 右侧数组下标
     * @return 完成一轮排序后基准所在的下标(中点)
     */
    private static int partition(int[] A, int p, int r) {
        //优化，在p,r,mid之间，选一个中间值作为基准
        int midIndex = p + (r - p) / 2;//中间下标
        int midValueIndex = -1;//中值下标
        if (A[p] <= A[midIndex] && A[p] >= A[r]){
            midValueIndex = p;
        }else if(A[r] <= A[midIndex] && A[r] >= A[p]){
            midValueIndex = r;
        }else {
            midValueIndex = midIndex;
        }
        swap(A,p,midIndex);
        int pivot = A[p];//把第一个元素作为基准
        int left = p + 1;//左侧指针
        int right = r;//右侧指针
        while (left <= right) {//当左侧指针在右侧指针右边时退出循环
            while (left <= right && A[left] <= pivot) {//左侧指针扫描到的元素<=基准，左侧指针右移
                left++;
            }
            while (left <= right && A[right] > pivot) {//左侧指针扫描到的元素>基准，右侧指针左移一位
                right--;
            }
            if (left < right) {
                swap(A, left, right);
            }
        }
        //以上过程完成之后，left一定指向第一个大于基准的(并且left右边全都大于基准)，而right一定指向最后一个小于等于基准的(并且right左边全都小于等于基准)
        //我们要将基准放在中间的一个合适位置，这个位置就是当前right的位置
        swap(A, p, right);
        //上一行已经将基准放在了合适的位置(bigger指向的位置)，返回这个基准所在的位置
        return right;
    }

    /**
     * 交换数组中两个元素的方法
     */
    private static void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}
